package com.wenhao.leetcode.medium;

import java.util.*;

/**
 * 题目：https://leetcode-cn.com/problems/lru-cache/
 * LRU 缓存机制
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-07-05 12:30
 */
public class LRUCache {

    class Node {
        Integer key;
        Integer value;
        Node next;
        Node pre;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.get(2);
        lruCache.put(2,1);
        lruCache.put(2,2);
        lruCache.get(2);
        lruCache.put(1,1);
        lruCache.put(4,1);
        lruCache.get(2);
    }

    Map<Integer,Node> map;
    int capacity;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.capacity = capacity;
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Node result = map.get(key);
        if (result != null) {
            moveToLast(result);
            return result.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node temp = map.get(key);
        if (temp == null) {
            Node node = new Node();
            node.value = value;
            node.key = key;
            addToLast(node);
            if (map.size() == capacity) {
                map.remove(head.next.key);
                pop();
            }
            map.put(key,node);
        } else {
            temp.value = value;
            moveToLast(temp);
        }
    }

    private void pop() {
        map.remove(head.next.key);
        head.next = head.next.next;
        head.next.pre = head;
    }

    private void moveToLast (Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        addToLast(node);
    }

    private void addToLast(Node node) {
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    }
}
